package com.yulongtian.weekCompetition.month202303.week01;

import java.util.Arrays;

/**
 * @author yulongTian
 * @create 2023-03-05 11:02
 */
public class Test13 {
    public static void main(String[] args) {
//        int[] arr = new int[]{557663, 280817, 472963, 156253, 273349, 884803, 756869, 763183, 557663, 964357, 821411, 887849, 891133, 453379, 464279, 574373, 852749, 15031, 156253, 360169, 526159, 410203, 6101, 954851, 860599, 802573, 971693, 279173, 134243, 187367, 896953, 665011, 277747, 439441, 225683, 555143, 496303, 290317, 652033, 713311, 230107, 770047, 308323, 319607, 772907, 627217, 119311, 922463, 119311, 641131, 922463, 404773, 728417, 948281, 612373, 857707, 990589, 12739, 9127, 857963, 53113, 956003, 363397, 768613, 47981, 466027, 981569, 41597, 87149, 55021, 600883, 111953, 119083, 471871, 125641, 922463, 562577, 269069, 806999, 981073, 857707, 831587, 149351, 996461, 432457, 10903, 921091, 119083, 72671, 843289, 567323, 317003, 802129, 612373};
//        int[] arr = new int[]{4, 7, 8, 15, 3, 5};
        int[] arr = new int[]{833293, 342059, 54541, 361807, 982061, 933923, 424967, 778717, 673297, 239587, 589493, 532453, 829187, 177967, 181081, 245417, 875731, 180247, 334987, 948929, 67631, 126001, 969083, 192193, 532633, 719779, 142357, 904759, 480967, 399433, 14407, 440047, 425701, 159617, 467213, 62533, 85549, 757171, 273521, 405037, 12101, 504787, 705883, 884201, 413251, 527671, 97103, 479777, 422881, 814129, 878737, 199559, 272399, 168599, 663937, 225523, 95483, 432143, 198221, 324329, 968089, 237901, 442979, 984299, 335077, 753569, 630689, 483719, 464119, 600949, 833711, 650329, 256967, 684977, 664117, 308303, 172981, 513053, 223241, 896479, 976471, 598687, 782011, 995959, 704999, 514417, 158231, 148639, 410383, 875521, 399149, 179381, 635959, 124367, 761927, 238423, 752033, 245513, 530279, 169097, 919033, 199687, 43793, 219979, 292693, 502441, 486433, 102953, 630701, 560761, 746191, 556609, 699151, 809891, 155203, 737327, 211129, 197621, 330227, 495751, 415553, 59723, 523177, 240883, 280223, 336653, 924683, 862739, 681041, 321163, 74653, 603077, 356093, 506213, 708137, 534307, 1499, 457097, 862943, 195089, 747833, 169751, 236869, 358291, 958343, 483643, 935587, 122509, 256541, 593711, 258787, 296071, 826667, 72031, 375163, 79621, 92461, 639257, 201101, 361421, 392087, 34721, 427997, 243583, 257863, 273323, 247073, 922511, 413683, 986207, 43403, 629873, 201517, 703471, 936889, 529673, 212227, 549403, 140761, 58661, 223007, 73361, 702173, 949159, 73637, 72661, 907139, 679361, 582971, 248203, 404269, 563813, 425059, 631583, 285827, 566977, 634097, 106129, 771889, 431329, 995399, 233, 841207, 93889, 313949, 646577, 945899, 115117, 467527, 417553, 411937, 145931, 234863, 563411, 769661, 140893, 159667, 406883, 378011, 70921, 765059, 802531, 542281, 966041, 119299, 370687, 776921, 996647, 106033, 380459, 386249, 934763, 417203, 366479, 668533, 658649, 218737, 108011, 757943, 473117, 438521, 392611, 296843, 805279, 908581, 579713, 788159, 603667, 84221, 989293, 849461, 952247, 207541, 202309, 153523, 188473, 225749, 860059, 427013, 389083, 231277, 997091, 473951, 91079, 655211, 77017, 623423, 219017, 47933, 863959, 516247, 99487, 286801, 146777, 834497, 333563, 928849, 176977, 202183, 873463, 637243, 23677, 730397, 649487, 143489, 78301, 166931, 724121, 215503, 480731, 423179, 385559, 137117, 664507, 972001, 323903, 77977, 920419, 70849, 27803, 578327, 515839, 619139, 317089, 282767, 106759, 15749, 56359, 477221, 69809, 528833, 232643, 454709, 644863, 430121, 367823, 923987, 145417, 26267, 690491, 334661, 848087, 765851, 876301, 70207, 512543, 692051, 125053, 56311, 68443, 434881, 920519, 109147, 810923, 406073, 874063, 547097, 397763, 822389, 4297, 589349, 395537, 711133, 613337, 503927, 576659, 387917, 307169, 789967, 532153, 108401, 609991, 1543, 955501, 22259, 717817, 178333, 982231, 282563, 188137, 306347, 734659, 178931, 337327, 713753, 363061, 165383, 410983, 972991, 265403, 372803, 207457, 465799, 304879, 229771, 390347, 874847, 698939, 857309, 845333, 920357, 60271, 378253, 521393, 403861, 386569, 987911, 398011, 830363, 812299, 574289, 74747, 125107, 693757, 511859, 219953, 557863, 199037, 319489, 471061, 948287, 199741, 178639, 484531, 101051, 926183, 1399, 394811, 859603, 787751, 423067, 772867, 341347, 797767, 755593, 376081, 720947, 968519, 809399, 709679, 533633, 477497, 201673, 118043, 33533, 891907, 466651, 554899, 513103, 533713, 165349, 839957, 640099, 577097, 51449, 113111, 972227, 752699, 285749, 464081, 945457, 908959, 176221, 720847, 445891, 251501, 625979, 44753, 399911, 154061, 892513, 75391, 300229, 577537, 234989, 355321, 834641, 947119, 189691, 586577, 833293, 242681, 798251, 464003, 177893, 120997, 472349, 458219, 133949, 722077, 504143, 433813, 625307, 285871, 191459, 800923, 156967, 552899, 770801, 603283, 695777, 879113, 737563, 436853, 950347, 236261, 571111, 774661, 946031, 321469, 762539, 719717, 60107, 94723, 384299, 924731, 891389, 909281, 295153, 502921, 8719, 358153, 602267, 841913, 905249, 844651, 713407, 181549, 192173, 706133, 958669, 801197, 197221, 218641, 585383, 518083, 841021, 802733, 587947, 101141, 922973, 379699, 130043, 539947, 541237, 384247, 657361, 491951, 559099, 288481, 567979, 635977, 4673, 789511, 435037, 319469, 396443, 853693, 981037, 425317, 884497, 314357, 470333, 167729, 79043, 741341, 138433, 681271, 978473, 686611, 242261, 396713, 731483, 68611, 334511, 220411, 850727, 668579, 270379, 890887, 912217, 993079, 451933, 632857, 39323, 746117, 532027, 231611, 754223, 419051, 983113, 606791, 794009, 17351, 440581, 13931, 880687, 949147, 820177, 217439, 11399, 652903, 414053, 298559, 110491, 951109, 861191, 449311, 380417, 134257, 890737, 358909, 256981, 50789, 24181, 107837, 966319, 130981, 254447, 971479, 33811, 319327, 17881, 99971, 153067, 847993, 736097, 871837, 951437, 374909, 295439, 371561, 897691, 508957, 676349, 185189, 610849, 128923, 292679, 556069, 231293, 39521, 549641, 726811, 983531, 932761, 550441, 110261, 214469, 403331, 77647, 714947, 392437, 704581, 153757, 765503, 688763, 786001, 90523, 895553, 925181, 778693, 268969, 947711, 114199, 4421, 384623, 549379, 185291, 612889, 316469, 614843, 820343, 953237, 871789, 613153, 14843, 774119, 343897, 757327, 12301, 385741, 482441, 360407, 830153, 410281, 712601, 569809, 20743, 438983, 49727, 909737, 961459, 218987, 275573, 41969, 318841, 554189, 384367, 175853, 417899, 516437, 356761, 253553, 982777, 10939, 869489, 895051, 543241, 697703, 712819, 369979, 880331, 324391, 416201, 506941, 6949, 106031, 470077, 852623, 713357, 599387, 305231, 327757, 694123, 513047, 715373, 710813, 151871, 507827, 945431, 854431, 435221, 475859, 789169, 774601, 817321, 935303, 951283, 907391, 969461, 705409, 905701, 426163, 335029, 470089, 593629, 540437, 746563, 596243, 902591, 397037, 642683, 785923, 463907, 413087, 781139, 182587, 108863, 396199, 164839, 804989, 777979, 67759, 192271, 120737, 898153, 468353, 757829, 422111, 583501, 210361, 549587, 4261, 720943, 706213, 992723, 307033, 714851, 242989, 122497, 32917, 900491, 417737, 478453, 799343, 905161, 801301, 760499, 848761, 560083, 5021, 53437, 716783, 908381, 508019, 797611, 184477, 810013, 477839, 716171, 351469, 179899, 856487, 988951, 920947, 101293, 851087, 991343, 489553, 358219, 748637, 254147, 922631, 273739, 260089, 865717, 924359, 777617, 649771, 879673, 842339, 110917, 667321, 945937, 692059, 217241, 885517, 192749, 705437, 697457, 274081, 728423, 792983, 884131, 241771, 270961, 960941, 282911, 499211, 776551, 906431, 988577, 127051, 772537, 124249, 508987, 265541, 97459, 182041, 270563, 941011, 783661, 518803, 796561, 218081, 583421, 862157, 161971, 314827, 681781, 54421, 509623, 744949, 818093, 49019, 964297, 404843, 419191, 667091, 972481, 233477, 302297, 17737, 321007, 533089, 23291, 749851, 720683, 313679, 952573, 48991, 81973, 894391, 51679, 731933, 858113, 372461, 543383, 40493, 552649, 402419, 713329, 385493, 734567, 769289, 564391, 181967, 155387, 605893, 744503, 289361, 163633, 471179, 83299, 642737, 749461, 137491, 979423, 463643, 154279, 598967, 296579, 598651, 226241, 515519, 277741, 468371, 690511, 865069, 387083, 288649, 272093, 975281, 520703, 324179, 8363, 340859, 631717, 86981, 84871, 162629, 573719, 730277, 195973, 211873, 415187, 377687, 448993, 644881, 600529, 534949, 82013, 275167, 565247, 265231, 254369, 167071, 958367, 768881, 53993, 744811, 377071, 755681, 771091, 467879, 119419, 607219, 383393, 19709, 42331, 277279, 284927, 496789, 725071, 337583, 326449, 5939, 85577, 889309, 365773, 281971, 732631, 487283, 842767, 863509, 105491, 828209, 21577, 521251, 412651, 259781, 92227, 73721, 379013, 32411, 357347, 495797, 575923, 546391, 564013, 902201, 539533, 571789, 607049, 2099, 974971, 373063, 837601, 783257, 785591, 169859, 696323, 754207, 674929, 614321, 56393, 273709, 22003, 720931, 152723, 845941, 252463, 471241, 84653, 131797, 47419, 67961, 478763, 792643, 209543, 866471, 35099, 11119, 998617, 798799, 675551, 325001, 469487, 601949, 591457, 844517, 762061, 65551, 982117, 11243, 230327, 683477, 927361, 847051, 121369, 587551, 369023, 367, 984881, 245087, 155017, 695843, 77419, 225347, 53279, 85037, 171713, 34327, 678553, 556769, 529307, 935777, 984437, 442997, 118163, 28201, 185831, 604559, 761713, 3911, 19843, 959377, 174137, 746267, 191237, 957361, 650327, 795349, 315551, 134263, 988607, 314239, 255503, 672521, 605323, 245753, 780257, 799483, 528403, 113567, 479569, 929057, 726809, 714907, 658117, 878299, 575791, 283193, 423791, 195541, 98459, 584347, 191671, 434237, 93059, 680417, 536267, 553463, 669377, 78479, 21401, 269029, 57787, 430193, 469907, 745817, 97039, 344291, 386839, 616411, 637003, 714113, 403703, 183881, 736607, 900821, 42239, 312619, 795643, 110947, 924529, 148957, 799741, 442879, 15737, 22171, 884341, 392477, 298621, 332687, 165931, 115613, 942787, 124199, 701179, 343087, 27527, 286061, 727781, 560929, 861647, 235747, 178417, 484243, 398059, 456091, 626363, 673529, 918497, 380333, 62383, 644557, 732709, 930197, 114571, 253157, 809719, 658379, 176903, 181903, 769469, 702587, 676883, 610331, 171877, 917753, 997379, 274103, 683071, 6323, 440939, 781919, 904663, 389999, 865817, 394259, 729661, 587267, 151703, 365291, 944711, 76471, 159157, 560411, 790241, 382567, 504479, 522227, 904369, 452821, 874661, 929639, 630169, 718943, 44257, 37573, 733619, 69029, 885869, 146987, 503743, 547171, 919189, 121369, 668209, 861647, 928679, 807973, 52639, 858103, 969919, 281363, 435997, 883489, 184609, 750083, 832631, 294781, 470627, 609289, 928597, 213533, 341629, 371257, 217207, 763001, 55411, 867397, 93827, 334493, 897817, 497597, 353681, 664561, 88037, 313153, 975731, 270437, 250813, 194681, 441443, 58451, 633803, 234043, 67073, 448597, 400157, 405947, 795917, 473471, 24697, 438953, 479371, 490417, 767813, 17443, 27329, 888989, 767513, 314159, 922283, 93563, 113537, 637909, 929941, 953347, 949903, 631357, 129209, 938563, 135019, 617363, 783803, 709921, 870097, 40853, 755789, 733097, 454313, 255121, 640333, 142979, 706291, 744661, 599983, 405901, 399769, 591559, 364271, 239539, 246361, 57041, 624139, 769259, 761521, 686723, 636241, 3923, 173839, 987593, 607081, 207799, 504607, 271639, 724267, 185077, 123757, 29803, 874711, 354043, 139241, 989579, 402107, 827929, 686729, 574619, 455827, 136777, 265339, 448801, 563021, 514357, 290183, 461467, 213949, 302851, 817433, 469891, 345673, 569831, 58031, 860507, 255961, 340127, 697271, 768197, 497671, 4391, 22697, 123553, 211859, 421699, 200591, 543139, 921353, 74131, 333679, 561229, 538411, 143827, 17489, 954677, 819367, 880057, 175673, 331013, 733321, 441517, 804943, 938869, 632777, 566173, 47491, 63823, 27109, 82721, 160753, 542719, 431063, 577193, 781409, 803027, 485263, 108947, 526027, 214213, 262693, 80737, 851597, 52127, 830899, 336703, 528391, 357977, 436253, 294649, 154087, 79139, 60103, 436181, 87793, 298153, 458363, 765953, 95327, 97367, 441751, 894997, 558529, 114761, 61331, 971357, 965407, 970069, 617509, 79111, 15973, 679417, 651289, 174367, 393191, 951659, 622723, 219757, 722291, 131611, 271807, 299951, 564881, 12073, 792101, 670303, 585413, 805187, 634747, 800053, 226937, 356479, 238103, 600751, 209359, 152017, 906847, 654301, 72503, 99139, 816547, 41953, 963031, 132047, 966817, 158269, 506911, 157793, 436739, 65183, 442903, 373343, 732497, 371981, 226753, 554431, 139537, 885427, 574033, 448309, 880423, 701627, 453133, 121523, 831847, 48533, 601819, 177383, 311869, 933019, 599479, 575647, 572941, 122453, 925669, 875773, 958777, 59651, 715873, 467471, 269389, 848789, 981049, 3023, 852347, 64633, 31147, 152519, 439511, 914219, 446717, 265417, 324953, 812939, 387089, 331957, 612751, 269389, 542497, 328651, 721057, 108769, 445271, 267713, 860369, 310889, 398989, 457319, 115757, 773153, 721051, 289171, 59419, 316507, 469237, 721319, 885679, 481769, 501229, 278753, 538303, 878089, 174617, 458629, 753689, 908627, 663161, 11579, 81547, 682739, 227609, 920869, 86561, 307633, 659171, 191441, 378713, 253049, 819673, 847151, 676861, 432301, 96911, 4909, 714521, 717527, 610837, 744019, 44819, 124001, 63589, 16741, 501271, 847933, 411409, 112297, 411641, 846421, 387913, 604477, 767909, 15683, 982103, 952657, 351811, 394601, 528971, 150743, 387109, 54601, 50093, 24091, 658579, 45697, 783283, 984911, 74897, 711859, 813443, 739397, 895319, 401537, 438967, 823547, 879287, 28607, 562021, 633467, 499519, 31873, 178753, 911291, 906403, 938983, 570001, 883411, 367163, 642769, 935093, 68891, 93199, 900761, 549943, 605261, 836153, 837073, 580259, 763967, 266281, 787337, 977507, 566089, 412637, 604517, 756709, 150151, 405473, 539093, 231719, 626761, 619007, 78721, 459353, 347987, 821497, 298373, 704029, 30047, 239977, 486179, 529007, 720661, 616391, 106277, 926357, 422869, 355009, 204437, 191801, 756839, 276707, 490223, 260453, 363403, 412481, 995833, 512903, 40801, 790261, 513481, 186481, 714881, 326873, 32957, 450019, 954203, 756467, 342481, 981707, 867547, 206593, 475841, 509281, 627961, 244901, 599831, 732283, 760267, 212869, 307537, 224683, 630719, 695269, 620831, 273569, 982183, 969671, 667129, 11827, 964357, 203663, 633037, 405089, 205993, 246497, 69383, 623393, 712961, 245471, 288877, 681787, 295693, 308929, 64793, 97423, 835909, 105337, 849923, 320149, 513439, 134227, 132361, 109517, 819017, 920561, 148439, 860417, 656651, 422311, 263729, 21817, 982613, 246833, 296183, 492403, 255049, 788309, 911621, 475973, 895681, 674987, 981587, 838939, 560669, 13451, 33581, 383179, 776119, 187123, 187181, 211433, 449689, 130681, 756709, 682679, 868081, 164513, 276961, 622103, 567653, 769169, 671477, 420163, 878039, 681841, 37619, 561961, 401909, 919031, 106937, 398273, 950869, 153443, 497297, 227533, 529027, 174101, 455491, 288179, 49477, 138559, 35311, 259537, 872549, 333019, 455977, 80221, 805573, 876893, 901141, 62171, 819389, 788933, 440179, 652999, 661253, 278219, 655859, 461843, 883613, 4447, 555349, 683783, 603257, 263239, 458407, 844453, 453631, 933433, 369913, 843881, 302843, 768923, 903569, 776201, 366383, 971051, 691001, 341771, 811231, 717463, 204173, 755267, 495119, 338687, 838459, 715969, 639053, 50441, 387463, 612037, 855919, 60733, 612613, 341171, 290711, 219763, 215689, 979519, 928817, 833117, 211493, 860087, 261389, 711727, 64381, 66791, 583007, 672587, 84401, 841019, 680971, 457799, 620731, 839539, 851569, 746411, 495613, 167317, 808993, 814699, 328331, 352831, 989249, 405857, 34591, 78139, 2879, 513839, 167633, 488617, 218963, 833179, 511351, 294181, 701629, 79841, 5059, 444209, 852833, 40151, 884371, 1907, 574547, 295787, 533989, 381559, 324319, 570553, 218279, 352753, 655583, 516877, 919319, 486943, 802709, 327473, 920197, 792641, 752183, 166667, 541901, 621031, 722027, 655087, 354763, 147289, 179369, 172807, 789959, 864151, 956303, 545203, 279751, 54437, 63697, 20287, 513991, 304363, 373339, 337859, 157291, 312107, 728713, 314351, 834787, 70687, 62473, 742541, 389381, 847789, 552887, 673, 418177, 219409, 852149, 95287, 628049, 82981, 182603, 721351, 5233, 518131, 579961, 74941, 800783, 327079, 27091, 55079, 565049, 10321, 864883, 348643, 574501, 494101, 99119, 12823, 426383, 1097, 412571, 586153, 407669, 506047, 135607, 131111, 697601, 765389, 626663, 137239, 945787, 230449, 813097, 102829, 109367, 673579, 112951, 791519, 185557, 948089, 99401, 507347, 585071, 24977, 665549, 151007, 428873, 872353, 411287, 682901, 90437, 123581, 512797, 434927, 539993, 989921, 201581, 119827, 865783, 824191, 746033, 664843, 777677, 820643, 531337, 918481, 201947, 111431, 92693, 887923, 896443, 59999, 32801, 318211, 881743, 319927, 639833, 111697, 898243, 867463, 24481, 303689, 184291, 37117, 276371, 712171, 706669, 580691, 316493, 28901, 820711, 520549, 798043, 184241, 944963, 842489, 109037, 338573, 325181, 357809, 172519, 54059, 434743, 50551, 585727, 946663, 251887, 912979, 336499, 134153, 452953, 671339, 162649, 612331, 612809, 321889, 382429, 887717, 411727, 253307, 848399, 787903, 456409, 201611, 719659, 109199, 404113, 638371, 677563, 526499, 201511, 255023, 939973, 675713, 75169, 579641, 242173, 234799, 355027, 518327, 337861, 335299, 78193, 102829, 790897, 184997, 899893, 958871, 926957, 367201, 943249, 157061, 604781, 447053, 339161, 189697, 679879, 665921, 8963, 224629, 342341, 702407, 630281, 202361, 714971, 357619, 686057, 450847, 22709, 474899, 474433, 579353, 130957, 996617, 380059, 162593, 62639, 748711, 267389, 776471, 41453, 616433, 910849, 644717, 266891, 14051, 158407, 10391, 540307, 836347, 833281, 428807, 101503, 356981, 856483, 991621, 203213, 521669, 966557, 59123, 720221, 940801, 421783, 261799, 729173, 172607, 17299, 994039, 209227, 422567, 135319, 425291, 17923, 257189, 915143, 319037, 924097, 650609, 535319, 8447, 838193, 619561, 543427, 107827, 996211, 232709, 974279, 518261, 916169, 789589, 97523, 849061, 749219, 158303, 871337, 963607, 971753, 2269, 604319, 783259, 667829, 387031, 856693, 719441, 28859, 341041, 336373, 468133, 795877, 145121, 555823, 659689, 125627, 437527, 104987, 620821, 90793, 442763, 27617, 723379, 26449, 725587, 690583, 755077, 454109, 367181, 763613, 49547, 954977, 38543, 400711, 902449, 85121, 782183, 677239, 672283, 355529, 67273, 628423, 97841, 644911, 127591, 695069, 145637, 215983, 900037, 551731, 346117, 618841, 662047, 882577, 160877, 738863, 671161, 143053, 684683, 865511, 93187, 494141, 833429, 452233, 108761, 230819, 240607, 424889, 333071, 337853, 180317, 37517, 141131, 560621, 366889, 768437, 98729, 517619, 794201, 961447, 467123, 488153, 343667, 197753, 438281, 743059, 415559, 660949, 26669, 15349, 233641, 317159, 333929, 572963, 198413, 25411, 63199, 120779, 381097, 442327, 374887, 33347, 516319, 830911, 396881, 925033, 156913, 219971, 150827, 388691, 210277, 634679, 802019, 968959, 800909, 774107, 300331, 309167, 825049, 71, 128347, 273131, 680509, 773491, 437743, 480299, 590929, 738109, 198251, 496733, 694829, 379439, 609269, 217661, 774239, 842483, 483697, 201919, 948331, 635801, 711577, 609701, 70621, 203617, 75883, 311791, 722149, 647527, 389941, 958213, 544903, 301423, 34273, 985177, 932579, 69691, 439123, 877333, 496063, 656471, 26263, 926423, 429511, 514571, 420317, 431881, 216347, 278209, 328411, 92867, 27337, 114161, 395321, 769547, 740671, 545843, 467083, 136337, 3319, 15121, 427513, 745141, 739051, 632629, 180023, 996703, 88721, 432799, 297641, 81083, 708229, 207029, 717559, 372637, 198439, 941617, 165833, 209567, 366941, 33751, 4273, 885769, 62929, 412603, 129457, 413753, 136309, 561313, 490741, 404431, 648917, 238093, 841457, 747277, 654671, 958259, 430709, 786983, 3041, 904573, 300331, 300581, 315617, 943589, 301579, 882961, 413753, 801337, 328687, 108869, 496817, 330907, 692779, 805877, 833293, 467197, 211153, 68023, 21419, 57793, 755239, 302941, 921259, 778529, 246937, 795703, 350437, 13513, 871229, 214783, 984307, 978223, 433351, 501719, 228457, 769591, 313331, 958973, 602891, 407291, 130483, 673801, 449321, 394063, 497339, 834761, 537679, 717883, 826711, 266587, 56377, 554003, 209449, 70951, 366701, 793981, 361843, 644789, 153911, 202441, 740477, 911419, 883451, 381817, 831073, 669847, 577757, 550309, 720281, 35363, 991931, 783743, 10357, 658477, 314263, 655717, 828007, 751787, 616909, 407179, 749383, 702539, 19777, 763573, 484111, 266291, 133597, 565489, 884243, 502597, 558167, 540769, 198427, 735853, 414577, 358297, 758041, 239297, 980197, 301447, 700433, 465887, 968353, 44543, 888557, 841097, 822743, 182617, 142057, 215981, 222361, 451387, 953923, 837659, 915391, 429119, 3559, 519523, 148921, 527603, 527173, 398471, 596929, 653621, 342607, 694427, 183389, 596147, 748091, 958381, 766861, 889177, 987191, 984853, 347041, 382241, 310423, 448073, 148537, 463987, 244357, 821377, 927313, 1429, 359549, 150407, 208121, 875297, 724487, 257627, 79357, 503543, 256337, 971903, 653207, 782921, 37691, 95581, 580477, 430909, 61813, 437977, 146617, 875761, 184577, 472319, 518249, 604291, 630167, 655471, 880981, 44123, 440399, 868069, 411041, 699119, 548843, 377327, 682777, 32713, 903709, 557069, 572063, 423103, 178987, 386363, 185543, 311537, 372293, 738107, 148931, 416291, 175069, 968063, 154417, 875089, 765293, 114601, 41413, 501019, 451837, 34747, 995719, 617153, 229549, 724517, 148387, 168083, 405749, 628721, 234587, 537769, 55663, 554167, 194771, 1381, 279977, 5683, 168293, 568273, 880793, 933931, 11093, 456499, 765859, 540877, 166823, 223849, 994769, 15887, 832217, 909047, 620773, 737507, 888313, 92173, 989477, 523349, 160169, 595069, 121571, 671753, 936259, 618269, 879331, 995053, 639907, 83591, 19531, 925163, 570013, 27367, 426913, 742117, 839693, 245899, 432053, 840347, 463093, 537883, 560771, 612679, 460871, 456623, 562831, 166157, 443983, 445199, 706009, 285539, 16567, 583013, 593231, 917729, 851363, 845567, 368551, 258527, 155731, 268661, 364313, 572479, 288733, 761357, 128449, 520913, 145771, 674461, 185267, 948443, 521693, 482593, 383083, 280337, 912287, 248041, 707869, 42487, 67723, 713191, 284387, 344021, 491213, 181283, 455123, 349471, 703301, 239567, 950753, 714487, 986509, 2557, 469207, 771461, 582083, 166861, 19603, 771887, 91193, 960977, 23167, 448687, 224527, 280699, 57679, 309677, 562501, 267551, 638861, 561373, 5783, 739183, 112279, 734849, 608191, 438241, 856277, 465089, 320657, 899807, 693743, 650779, 598727, 367883, 662657, 982573, 943343, 638327, 67741, 220351, 971833, 85229, 127681, 51551, 862397, 375563, 650011, 409291, 259723, 730753, 27883, 288227, 879493, 143357, 343127, 740191, 37879, 152833, 433571, 498781, 382649, 587773, 132347, 611561, 754709, 419567, 361409, 144451, 118891, 82223, 705493, 812057, 7691, 171793, 92893, 93761, 523597, 332623, 942719, 120299, 227147, 763457, 508867, 692149, 267227, 944467, 198689, 860971, 212557, 540677, 461009, 970943, 610817, 876019, 116201, 291547, 444817, 74959, 366277, 393401, 331241, 473101, 562909, 118471, 587179, 381103, 282019, 389303, 244711, 816367, 656749, 127081, 647783, 90353, 308713, 38149, 205213, 184553, 155137, 509767, 12917, 870127, 334423, 467591, 800291, 430819, 266767, 872057, 696653, 235901, 423781, 808309, 906707, 298477, 289067, 413111, 220841, 265471, 913183, 100493, 377623, 255077, 232513, 711847, 215143, 898981, 416947, 974599, 873959, 842819, 833999, 673451, 333161, 988877, 726707, 970297, 451343, 572903, 386809, 982097, 141931, 887017, 471949, 716543, 586919, 333023, 105503, 265813, 555077, 451313, 512101, 763027, 691129, 569659, 558947, 600703, 305237, 455687, 124343, 282439, 748019, 696811, 6337, 777787, 277163, 790529, 618857, 435817, 796657, 624089, 16871, 855499, 351427, 739469, 627559, 87613, 864119, 687289, 93559, 508517, 334199, 350381, 136373, 285463, 599273, 584281, 304193, 145361, 745751, 778847, 110291, 84229, 327203, 38603, 727763, 159899, 631613, 867203, 715153, 889747, 98809, 269231, 863143, 793711, 98299, 64403, 461147, 745181, 392911, 171317, 652243, 635969, 65381, 986137, 443941, 451897, 373753, 49823, 534827, 362161, 432637, 157637, 386489, 646183, 650477, 464927, 381991, 646411, 765577, 590833, 82457, 561917, 87383, 583367, 572311, 491789, 609421, 700241, 594953, 937049, 932413, 630659, 37511, 830551, 657091, 868997, 697481, 303727, 309391, 415381, 586237, 932783, 137273, 169361, 346867, 804523, 635813, 14797, 169003, 188291, 794551, 333103, 455527, 303767, 386987, 383623, 801179, 981527, 123203, 666727, 812047, 12911, 912853, 209953, 939611, 595181, 166967, 149713, 130807, 571841, 641227, 744823, 642581, 44389, 489179, 69467, 542873, 35999, 169789, 557041, 890993, 505049, 192121, 519943, 592019, 638581, 357031, 978389, 994997, 964913, 314117, 61223, 843131, 70657, 860593, 524519, 700897, 427001, 582509, 419417, 192977, 279311, 151243, 145897, 565813, 30097, 246899, 773897, 441557, 693881, 879617, 813677, 275911, 699157, 488333, 122839, 169837, 156749, 22483, 613297, 672289, 262147, 686117, 209821, 215909, 767647, 120863, 991261, 708997, 946961, 685093, 960961, 528289, 296041, 280561, 751633, 505339, 521399, 284623, 901333, 723167, 401161, 865979, 199799, 248099, 387341, 908179, 983069, 222317, 986813, 624859, 881479, 105997, 992867, 601759, 198301, 334889, 126097, 919883, 273773, 973367, 66713, 817457, 604609, 439577, 805381, 457871, 301901, 418087, 521309, 757181, 86969, 688411, 485497, 636407, 315977, 385531, 268841, 943543, 487363, 151289, 611977, 793691, 476369, 527753, 693157, 435439, 817183, 263489, 466181, 930409, 403049, 778051, 135781, 704087, 481589, 882823, 766679, 536953, 208577, 850849, 989873, 992393, 374849, 682037, 828703, 182887, 917141, 536677, 209669, 102647, 714503, 846647, 47221, 936557, 786613, 824489, 658403, 420967, 828797, 160319, 631507, 508909, 538357, 907397, 949889, 577043, 994963, 58417, 457687, 615661, 117833, 447451, 363119, 422789, 283097, 140197, 27253, 805033, 889043, 313639, 984541, 671219, 657863, 93967, 607181, 974359, 577351, 357649, 392339, 331871, 725189, 352973, 719903, 503963, 38231, 984091, 85661, 102023, 873571, 123449, 215063, 345581, 504307, 840139, 663437, 464281, 654539, 104527, 963163, 576287, 422183, 772697, 145903, 714577, 96643, 761591, 720059, 648997, 667421, 221047, 114859, 584923, 689921, 35141, 330053, 632557, 208933, 195127, 158927, 509087, 627787, 112583, 138679, 285079, 85247, 798697, 684751, 21341, 489283, 93113, 524521, 31259, 194869, 552991, 366313, 223211, 700759, 744239, 966863, 312623, 810587, 832861, 443551, 330329, 489851, 160117, 41507, 170141, 515681, 791311, 371471, 378223, 647987, 988861, 29683, 530753, 244843, 36457, 314137, 941263, 267901, 108287, 9203, 575371, 704117, 130531, 884827, 746891, 654701, 628699, 897349, 460337, 521753, 625213, 123259, 819289, 931067, 896783, 931751, 86851, 933551, 652283, 543281, 90127, 152183, 71341, 931849, 271097, 917519, 684647, 111091, 474437, 464467, 759571, 58439, 47947, 508969, 329993, 97583, 178567, 922169, 365797, 686473, 609313, 73121, 45337, 757927, 308857, 484543, 72103, 456377, 135449, 859697, 651323, 250643, 708311, 934837, 256189, 514783, 47543, 333497, 287549, 885263, 368507, 587789, 536213, 32341, 618301, 75503, 958007, 162109, 818707, 358487, 957433, 67289, 664289, 110017, 592289, 667741, 25087, 998083, 933259, 547957, 510581, 230047, 28597, 613, 717317, 125063, 727633, 570733, 429547, 347801, 382867, 597131, 874459, 68767, 266447, 42071, 990707, 336799, 803333, 357353, 515663, 679999, 541349, 859981, 238781, 25771, 981637, 778091, 530983, 507317, 372689, 355093, 151381, 264487, 594203, 480929, 960053, 224759, 463523, 975313, 369581, 889069, 17681, 892189, 863783, 601631, 627383, 766471, 472643, 207481, 30839, 903407, 147227, 535061, 917591, 364031, 294167, 764399, 857047, 7019, 40283, 60443, 638959, 782393, 963253, 448633, 721219, 476587, 595451, 694619, 568691, 567569, 406817, 226813, 675539, 196279, 7489, 514243, 784981, 56167, 359419, 242483, 100591, 226381, 831253, 168263, 442601, 737423, 310861, 499819, 376657, 448519, 430999, 16427, 484327, 167861, 725423, 218401, 731389, 152081, 774377, 183761, 616793, 402139, 819491, 733399, 335897, 800861, 779657, 752177, 487973, 211219, 816047, 503053, 804803, 458819, 190063, 92857, 900259, 162209, 486817, 470461, 280997, 501217, 918353, 175601, 598987, 788413, 559781, 672967, 906767, 432959, 798227, 717293, 541661, 110023, 423587, 497663, 640837, 925913, 501931, 576439, 685723, 334771, 411127, 505979, 481199, 716531, 169217, 901781, 18287, 761377, 849839, 329317, 36913, 62423, 595339, 669763, 152203, 841283, 954167, 902977, 966613, 387307, 607349, 739283, 993241, 343829, 169159, 177283, 215693, 193463, 675751, 610271, 237487, 11423, 106123, 15643, 535999, 251033, 223697, 573197, 95651, 601849, 92951, 503563, 373181, 138053, 607153, 129959, 586067, 903257, 435751, 175303, 247997, 153001, 879271, 874957, 375223, 699521, 890459, 408337, 846397, 691121, 287149, 591259, 463291, 227363, 174071, 34651, 770639, 718813, 728911, 128311, 440501, 315899, 148949, 444641, 804371, 56527, 762989, 594401, 916999, 465781, 823747, 125591, 614563, 273857, 486103, 104561, 558629, 252391, 344821, 52153, 703819, 127529, 99707, 975523, 396833, 48589, 37021, 771607, 585337, 768371, 475613, 691337, 74453, 358277, 157411, 535991, 216577, 240719, 673643, 763417, 737573, 420149, 723851, 467293, 72091, 664757, 135151, 507383, 228139, 388253, 884453, 795239, 129553, 79559, 193357, 169957, 214763, 597407, 90271, 120767, 612877, 980591, 791599, 348937, 160009, 8807, 675889, 32537, 684869, 878893, 763901, 837359, 186959, 333911, 417649, 960889, 372413, 95009, 387973, 874891, 523997, 230653, 861823, 461093, 36809, 636473, 232877, 375467, 130253, 793229, 460111, 979543, 893479, 966409, 858833, 399481, 577931, 334547, 794363, 160499, 340283, 982621, 258551, 80107, 451397, 247501, 400417, 930289, 841231, 265579, 605233, 794413, 914941, 930179, 429511, 430741, 731851, 785573, 401473, 762121, 63727, 792793, 417733, 130729, 918209, 767857, 6133, 3823, 418189, 414949, 666403, 553759, 374587, 506251, 611333, 809453, 4013, 596983, 845447, 53923, 544501, 74551, 708437, 143719, 954097, 975071, 817603, 370897, 838633, 997, 484339, 337633, 280499, 322213, 788813, 961619, 654917, 418699, 613577, 661187, 363757, 391823, 118037, 335843, 635527, 739771, 985729, 774071, 623261, 467317, 648061, 391073, 573289, 198841, 980459, 759709, 517087, 847271, 199811, 385519, 206279, 575837, 199501, 280639, 291559, 21841, 737999, 402991, 141653, 154681, 127249, 507109, 871531, 91121, 190093, 661327, 343037, 615053, 799021, 625777, 186377, 955267, 806009, 845431, 227603, 698311, 787439, 995447, 402487, 402223, 140551, 749267, 439279, 466027, 924403, 99103, 657649, 218833, 654529, 437467, 854899, 801037, 96221, 86143, 129469, 969569, 854353, 445877, 199321, 443153, 758827, 159013, 97787, 972637, 946997, 582763, 753461, 906727, 84313, 411143, 599, 406577, 702379, 238397, 202859, 631483, 288767, 505231, 898483, 2903, 559583, 384497, 133349, 169657, 987227, 141301, 7963, 126127, 350767, 530129, 232433, 222041, 278947, 91237, 12347, 330383, 137713, 410173, 195443, 743363, 554051, 420001, 889139, 494567, 387403, 444307, 518467, 743987, 364291, 93377, 489901, 898823, 703033, 995461, 628591, 20369, 340957, 901907, 949523, 345259, 192229, 808627, 756869, 600053, 691979, 734477, 853799, 69427, 84919, 577873, 7159, 476167, 216991, 300977, 689279, 669167, 624851, 940787, 93329, 487247, 217001, 247381, 563263, 485371, 164429, 870517, 251857, 162677, 554117, 125441, 663517, 153107, 516161, 139457, 186391, 616051, 130211, 461233, 350747, 145037, 329873, 253769, 279919, 5147, 442777, 541193, 130439, 626713, 940889, 604171, 182011, 268937, 449077, 951089, 111833, 693397, 551281, 373489, 585437, 967721, 218227, 932441, 168109, 218423, 15401, 968437, 958627, 179779, 519667, 882169, 337759, 594697, 108061, 738953, 793673, 67547, 608611, 118529, 266129, 772001, 827087, 358301, 1049, 734819, 689981, 489677, 174049, 310867, 828643, 697201, 102071, 473167, 624593, 465821, 158293, 989839, 520717, 903607, 373273, 193811, 741413, 604931, 5639, 996871, 66851, 51197, 608471, 43717, 984211, 925399, 440171, 897269, 886069, 75253, 14563, 658351, 562943, 725999, 294179, 841013, 455149, 851203, 681113, 245671, 372817, 780917, 745189, 639937, 542603, 642973, 213449, 765353, 417491, 675029, 876193, 242413, 756961, 552137, 41593, 842393, 99497, 432983, 388273, 789749, 101483, 164587, 288293, 143257, 964021, 274909, 638819, 838693, 868331, 442571, 269713, 890063, 494561, 500923, 348563, 478243, 518801, 646519, 574657, 790093, 126989, 988837, 489011, 853133, 16903, 364601, 409477, 717271, 142231, 661877, 368273, 231017, 184777, 871763, 804689, 202717, 316223, 42643, 8537, 363809, 314693, 72767, 517417, 754133, 575957, 423221, 151523, 984121, 729503, 858931, 744641, 201767, 431191, 265427, 244243, 293659, 82499, 250049, 615521, 156419, 262511, 856637, 720413, 34631, 245533, 673399, 257371, 137341, 864131, 546461, 333271, 558703, 252893, 847703, 163927, 745753, 957431, 950329, 746177, 446969, 578131, 100363, 348769, 399401, 153991, 322327, 78941, 728743, 53759, 65957, 747713, 597127, 336223, 776947, 402881, 797593, 541049, 374557, 880819, 295541, 535133, 711539, 820093, 79349, 20899, 808589, 441953, 893489, 853703, 647321, 373327, 322319, 686843, 736037, 121867, 110989, 2851, 831539, 151253, 116483, 246907, 538397, 166273, 444007, 90263, 546841, 886019, 878077, 185833, 428411, 512761, 689341, 161591, 421279, 895813, 21773, 966751, 898063, 73819, 287321, 596291, 446441, 498469, 84523, 917843, 139511, 993919, 530659, 587131, 351293, 140929, 19699, 526307, 192817, 880949, 921841, 214009, 890419, 257869, 533719, 155453, 628301, 284111, 870433, 465739, 93047, 518129, 346217, 474413, 846353, 69001, 46523, 492587, 342971, 405677, 560149, 483239, 716483, 105751, 321817, 980363, 588733, 681557, 847787, 396943, 447173, 135599, 530267, 290657, 725579, 826571, 563723, 87649, 878597, 577307, 67399, 964213, 660251, 433049, 42197, 942901, 850529, 460181, 825637, 950231, 692929, 10627, 319567, 258421, 732331, 299389, 710779, 102983, 523927, 493807, 116539, 912167, 768049, 785129, 309851, 176087, 178207, 89021, 544007, 631753, 435371, 702887, 399173, 74149, 554347, 593233, 88817, 362723, 648653, 379849, 551107, 220789, 224129, 312583, 149861, 511909, 370891, 166183, 870847, 713563, 888323, 949951, 441811, 36307, 121421, 896617, 302837, 561059, 745601, 392069, 749143, 61843, 134639, 80747, 594551, 695263, 365851, 431671, 27271, 553457, 398143, 296441, 239119, 329101, 874373, 426331, 38393, 51977, 160813, 288559, 752519, 374939, 450391, 575257, 958673, 261379, 863833, 618329, 396509, 776059, 779357, 978853, 462983, 703991, 971591, 578537, 315097, 410009, 929641, 474169, 367027, 647099, 612341, 13037, 164251, 837467, 826351, 531877, 495361, 464213, 99017, 868783, 116531, 957871, 948067, 754651, 602197, 648871, 637409, 198017, 382001, 450071, 537599, 403537, 189229, 370247, 255383, 873497, 865499, 203209, 857011, 529547, 969509, 570359, 967501, 278489, 995471, 70351, 42863, 823741, 177679, 892159, 204067, 823829, 920011, 694747, 82129, 309121, 825421, 383951, 561551, 198013, 45263, 813041, 887267, 307759, 770167, 629177, 782329, 77069, 376583, 126359, 790331, 519217, 243839, 270841, 232081, 863003, 531667, 360973, 574061, 623263, 521657, 275711, 393007, 7793, 956113, 243553, 681997, 50627, 906869, 733639, 979787, 262459, 284897, 960829, 527407, 371719, 124433, 327499, 444463, 344273, 700103, 357169, 185993, 683087, 173773, 661009, 415783, 629929, 900587, 257239, 482017, 777643, 72869, 322097, 971713, 101681, 633221, 831643, 451441, 907213, 708859, 313507, 66463, 7193, 301789, 798331, 232963, 976309, 415133, 343817, 345769, 143833, 844141, 1493, 575251, 457253, 544613, 833893, 729713, 799301, 710371, 352399, 733283, 544627, 17359, 569617, 765319, 770359, 178643, 824749, 555029, 111869, 745951, 597967, 75329, 267277, 322351, 683377, 546943, 310819, 24247, 680993, 114203, 707789, 36871, 42649, 636043, 113143, 494647, 155801, 427951, 401017, 896719, 240371, 480919, 294023, 250963, 436061, 977591, 11489, 939061, 750137, 773693, 226409, 88523, 994363, 46187, 154877, 622049, 841277, 187513, 682009, 356141, 44189, 308129, 498439, 205823, 269177, 232699, 585049, 374783, 81421, 5351, 835591, 771691, 806261, 238649, 546869, 130379, 908101, 772231, 328333, 111593, 236713, 649981, 894559, 357739, 803857, 557831, 484303, 954851, 788393, 199403, 229903, 776513, 268921, 193763, 665801, 102677, 854617, 745027, 262697, 640793, 358229, 585493, 556219, 986597, 692539, 158161, 381287, 582181, 214631, 397687, 880909, 159793, 205399, 186601, 829867, 588937, 499663, 171707, 32587, 619477, 412333, 272693, 522737, 164239, 204481, 355087, 144173, 140689, 513167, 682673, 683843, 732863, 142657, 642151, 987143, 120907, 585037, 143177, 796591, 508549, 887101, 40213, 936827, 770059, 334379, 208961, 448843, 480661, 572137, 151799, 571589, 303379, 393539, 939769, 25633, 519619, 347981, 943751, 316343, 943699, 461441, 716449, 277261, 470531, 902179, 771517, 583351, 423287, 146389, 144541, 404323, 701023, 523741, 407471, 522017, 25373, 825733, 404699, 176159, 666737, 165397, 624391, 414769, 69911, 250301, 329209, 771997, 508033, 604369, 276953, 209327, 24379, 763751, 499883, 110563, 61603, 410999, 843397, 555683, 826697, 73091, 225989, 914213, 72937, 685019, 201577, 349841, 23981, 492409, 719683, 960199, 569903, 258499, 496849, 701731, 749467, 667123, 307367, 295847, 53299, 352459, 998681, 891017, 559001, 32749, 866927, 817777, 57347, 343891, 986287, 56783, 672041, 98057, 743923, 287747, 374149, 330359, 885977, 256577, 263597, 228077, 128981, 167221, 906427, 588647, 18301, 281159, 713243, 14369, 151631, 183979, 932333, 408011, 340909, 315103, 26557, 9421, 167911, 67421, 219809, 679169, 937477, 39719, 736679, 917513, 359483, 315517, 219707, 961703, 167177, 184559, 383101, 6661, 82339, 245317, 128591, 560689, 764591, 410833, 74317, 579239, 881357, 425083, 210533, 734869, 287251, 194891, 875263, 975049, 229309, 648971, 562043, 361769, 585149, 955891, 669481, 444623, 125659, 1051, 754981, 778553, 35227, 728839, 995167, 188933, 850807, 742619, 133781, 689093, 1471, 712909, 268637, 706159, 730603, 93701, 124951, 45569, 28843, 916501, 13163, 904999, 908317, 101701, 375233, 896549, 904067, 303283, 976823, 394943, 710873, 766531, 211639, 885811, 382939, 500111, 465281, 825739, 992363, 334541, 516457, 301027, 88741, 142609, 615259, 677791, 571093, 373621, 81527, 808637, 7757, 5801, 643547, 770177, 771359, 685613, 63853, 792797, 742909, 195407, 756131, 854533, 365929, 174917, 994621, 458879, 180379, 305033, 217561, 238967, 106541, 170473, 831541, 771863, 180949, 176317, 418799, 926309, 294461, 466079, 282881, 754109, 251861, 254729, 265247, 132697, 899851, 117571, 688627, 650759, 280751, 146191, 293639, 272927, 710909, 579499, 920539, 346111, 644977, 346739, 871657, 905909, 11069, 474787, 501659, 542557, 590099, 568853, 397301, 344161, 765847, 547, 466859, 101063, 287159, 538297, 659849, 922351, 70607, 620029, 5519, 888871, 690533, 580219, 376291, 103591, 209549, 599309, 20261, 29, 733373, 76091, 529973, 665239, 925469, 142873, 34127, 768623, 470213, 9923, 199679, 905551, 424729, 765587, 138139, 239531, 641203, 881911, 65537, 218131, 26723, 431441, 319399, 357131, 171637, 553193, 658607, 375607, 105649, 190097, 589793, 78341, 488827, 614743, 392149, 167777, 868459, 219959, 442789, 128399, 751921, 363683, 990169, 677447, 872789, 77041, 865349, 67129, 140617, 232819, 374441, 605309, 85837, 425071, 246689, 492523, 478001, 577523, 279119, 282157, 815527, 796709, 639137, 808481, 958393, 981173, 593083, 948659, 488651, 586819, 51893, 77659, 914491, 241601, 202381, 326939, 691051, 448727, 77269, 643301, 582563, 779693, 803171, 944561, 854047, 635339, 202753, 349399, 622091, 477539, 165857, 738263, 308323, 983317, 961729, 539509, 357613, 837077, 356591, 878413, 684119, 425857, 444883, 940369, 475327, 379667, 201623, 672131, 149333, 69067, 356933, 568751, 697087, 98869, 658979, 149899, 597451, 735739, 938659, 76579, 980261, 484577, 602311, 76873, 368737, 493249, 57991, 346721, 940931, 559591, 347731, 32423, 957949, 214069, 889727, 51473, 101323, 74531, 988453, 292717, 868111, 560437, 176191, 401773, 573371, 492397, 50227, 522839, 160933, 501953, 607493, 189713, 269393, 196499, 161527, 661849, 595373, 619753, 522881, 785311, 684433, 964861, 652567, 324073, 156521, 31231, 414697, 751799, 605113, 392033, 536017, 957823, 913247, 516959, 843361, 533219, 67057, 710683, 939511, 885509, 775393, 44917, 410857, 709991, 816223, 130051, 874873, 439357, 637067, 83701, 669391, 252037, 818353, 450841, 429431, 301759, 557057, 530183, 47653, 330167, 81883, 23321, 377459, 973801, 508961, 69737, 861877, 980107, 325993, 443591, 473089, 449437, 573883, 698419, 154937, 833783, 471173, 844043, 64237, 724729, 710459, 50957, 475483, 659047, 423481, 305521, 296011, 181603, 674767, 742057, 878147, 520649, 901133, 323333, 478697, 532691, 643639, 237157, 964571, 109363, 945179, 318077, 128339, 830411, 848941, 413477, 652357, 588779, 821879, 438827, 625477, 959863, 868369, 998843, 277577, 65929, 763391, 918439, 67789, 670363, 400067, 926741, 461309, 378761, 357817, 812807, 44027, 999377, 594193, 824947, 746957, 855061, 324557, 274259, 294773, 30727, 252223, 583213, 704251, 896353, 225289, 840061, 398669, 240473, 475649, 87323, 690187, 144899, 45481, 733829, 25679, 173141, 718051, 475511, 557027, 52237, 330679, 243487, 496891, 481021, 191231, 357389, 139, 453553, 130649, 237179, 344683, 325487, 950029, 701177, 104933, 926489, 989783, 596707, 343823, 745037, 327661, 946549, 408379, 634687, 108413, 515041, 430007, 658913, 365531, 425861, 193469, 804767, 80923, 127277, 123719, 272659, 440567, 335747, 786197, 376633, 657187, 13679, 509, 726917, 562693, 444713, 549229, 852613, 752603, 943153, 818123, 805853, 88427, 546947, 275201, 426161, 596749, 61043, 873617, 56009, 161141, 969041, 731189, 413711, 671603, 611027, 490019, 271021, 116689, 725519, 451057, 19759, 907813, 376931, 64661, 49663, 808837, 402559, 927853, 361727, 474839, 672913, 151673, 132241, 818371, 854171, 614417, 371699, 39229, 987391, 566413, 558179, 404977, 115981, 737767, 814633, 139333, 405499, 289469, 919421, 74687, 248621, 883429, 755087, 207443, 13249, 933677, 13327, 967763, 168089, 781589, 59063, 525913, 141829, 637817, 739369, 756719, 8017, 907163, 777349, 935003, 456553, 352237, 174649, 371549, 99961, 915851, 946549, 829267, 623387, 618173, 713863, 52937, 56003, 586433, 548501, 284681, 127423, 157901, 571873, 414521, 276007, 370613, 647399, 78307, 462937, 428047, 110863, 171697, 297881, 964753, 601297, 136343, 385261, 366467, 507431, 211369, 9533, 431369, 779231, 612169, 584791, 875969, 707501, 978521, 424091, 610187, 998273, 257351, 361679, 439661, 231349, 900293, 728953, 822907, 823421, 182471, 646873, 100609, 876131, 135101, 401411, 848531, 622613, 529051, 930689, 381629, 19141, 474533, 235489, 652541, 696313, 541571, 270329, 162289, 984167, 957611, 219613, 4943, 582623, 668989, 229547, 616003, 672901, 104597, 392101, 282661, 275929, 375247, 874103, 569851, 128257, 593851, 289741, 961627, 675133, 533593, 31277, 649123, 825329, 851549, 745873, 873109, 546349, 686891, 441157, 92177, 628709, 784513, 584471, 3373, 3209, 758753, 646421, 201007, 957959, 76649, 825161, 211063, 910307, 44263, 616243, 479153, 934009, 774467, 579541, 908813, 652331, 697181, 883639, 369143, 451579, 263269, 364801, 332053, 352607, 466733, 938051, 248077, 781661, 316097, 838771, 68881, 136177, 905227, 234139, 187633, 334177, 594899, 775811, 34847, 239851, 329233, 944527, 197909, 971237, 14879, 421847, 419183, 798937, 216373, 743321, 158227, 498749, 472691, 596941, 63649, 137077, 118669, 141671, 232003, 260111, 840991, 776987, 676037, 382693, 625181, 969767, 810389, 474319, 915911, 206519, 771073, 299359, 879973, 105023, 523463, 662917, 98909, 336527, 106213, 418129, 706919, 794449, 857629, 459421, 280409, 52163, 23189, 915839, 444029, 367189, 841259, 120929, 318271, 715961, 36523, 992021, 434167, 510773, 6793, 901591, 977369, 16883};
        System.out.println(findValidSplit(arr));
    }

    //3640
    public static int findValidSplit(int[] nums) {
        System.out.println(nums.length);
        int left = 0;
        int right = nums.length - 2;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(nums, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    public static boolean check(int[] nums, int i) {
        //前面的与后面的数都互质
        for (int j = 0; j <= i; j++) {
            for (int k = i + 1; k < nums.length; k++) {
                if (gcd(nums[j], nums[k]) != 1) {
                    return false;
                }
            }
        }
        return true;
    }

//    //暴力超时  29/39
//    public static int findValidSplit(int[] nums) {
//        System.out.println(nums.length);
//        for (int i = 0; i <= nums.length - 2; i++) {
//            System.out.println(i);
//            boolean flag = true;
//            //前面的与后面的数都互质
//            for (int j = 0; j <= i; j++) {
//                for (int k = i + 1; k < nums.length; k++) {
//                    if (gcd(nums[j], nums[k]) != 1) {
//                        flag = false;
//                        j = i;
//                        break;
//                    }
//                }
//            }
//            if (flag) {
//                return i;
//            }
//        }
//        return -1;
//    }

    //求最大公约数
    private static int gcd(int a, int b) {
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        int r = 0;
        while (b != 0 && (r = a % b) != 0) {
            // 若余数不为 0
            a = b;
            b = r;
        }
        return b;
    }

}
